package 双指针;

import java.util.Arrays;
/*力扣 611题
找一个数组能组成三角形的最大组数
双指针算法：1.先将数组从小到大排序
          2.然后设立A=left,B=right,C=i三条边
          3.c为最大边，然后当left+right>c 能组成三角形，反之则不可，
          当left+right>c时，因为left为最小数，则right-left 之间的数都可组成三角形
          4.当left+right>c时，right--,当left+right<=c时，left++
* */
public class 有效三角形个数 {

    public static int triangleNumber(int[] nums) {
        //1.优化排序
        Arrays.sort(nums);
        //2.利用双指针解决问题
        int n=nums.length, ret=0;
        for(int i=n-1;i>=2;i--){//先固定最大的数
            //利用双指针快速统计出符合要求的三元组的个数
            int right=i-1;
            int left=0;
            while(left<right){
                if(nums[right]+nums[left]>nums[i]){
                    ret+=right-left;
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int []nums={2,2,3,4};
        int e=triangleNumber(nums);
        System.out.println(e);
    }
}
